package uestc.lj.leetcode.day1;


import java.util.*;

/**
 * @Author:Crazlee
 * @Date:2021/11/20
 */
public class Solution {

	public int findLHS(int[] nums) {
		Arrays.sort(nums);
		int begin = 0;
		int res = 0;
		for (int end = 0; end < nums.length; end++) {
			while (nums[end] - nums[begin] > 1) {
				begin++;
			}
			if (nums[end] - nums[begin] == 1) {
				res = Math.max(res, end - begin + 1);
			}
		}
		return res;
	}

	public boolean validPalindrome(String s) {
		int low = 0, high = s.length() - 1;
		while (low < high) {
			char c1 = s.charAt(low);
			char c2 = s.charAt(high);
			if (c1 == c2) {
				low++;
				high--;
			} else {
				return validPalindromeAfterDelectChar(s, low + 1, high) || validPalindromeAfterDelectChar(s, low, high - 1);
			}
		}
		return true;
	}

	private boolean validPalindromeAfterDelectChar(String s, int low, int high) {
		for (int i = low, j = high; i < j; i++, j--) {
			char c1 = s.charAt(i);
			char c2 = s.charAt(j);
			if (c1 != c2) {
				return false;
			}
		}
		return true;
	}

	public boolean isPalindrome(String s) {
		int left = 0;
		int right = s.length() - 1;

		while (left <= right) {
			if (!Character.isLetterOrDigit(s.charAt(left))) {
				left += 1;
			} else if (!Character.isLetterOrDigit(s.charAt(right))) {
				right -= 1;
			} else {
				char char1 = Character.toLowerCase(s.charAt(left++));
				char char2 = Character.toLowerCase(s.charAt(right--));
				if (char1 != char2) {
					return false;
				}
			}
		}
		return true;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public ListNode[] listOfDepth(TreeNode tree) {
		List<ListNode> list = new ArrayList<ListNode>();
		Deque<TreeNode> queue = new ArrayDeque<>();
		queue.offer(tree);
		while (!queue.isEmpty()) {
			int size = queue.size();
			ListNode dummy = new ListNode(0);
			ListNode cur = dummy;
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				cur.next = new ListNode(node.val);
				cur = cur.next;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			list.add(dummy.next);

		}
		return list.toArray(new ListNode[list.size()]);
	}

	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		return process(root).isBalanced;

	}

	public static class ReturnType {
		public boolean isBalanced;

		public int height;

		public ReturnType(boolean isBalanced, int height) {
			this.isBalanced = isBalanced;
			this.height = height;
		}
	}

	public static ReturnType process(TreeNode root) {
		if (root == null) {
			return new ReturnType(true, 0);
		}
		ReturnType left = process(root.left);
		ReturnType right = process(root.right);
		int height = Math.max(left.height, right.height) + 1;
		boolean isBalance = left.isBalanced && right.isBalanced && Math.abs(left.height - right.height) < 2;
		return new ReturnType(isBalance, height);
	}

	public boolean isValidBST1(TreeNode root) {
		if (root == null) {
			return true;
		}
		return process2(root).isBST;
	}

	public static class ReturnData {
		int min;
		int max;
		boolean isBST;

		public ReturnData(int min, int max, boolean isBST) {
			this.min = min;
			this.max = max;
			this.isBST = isBST;
		}
	}

	public static ReturnData process2(TreeNode root) {
		if (root == null) {
			return null;
		}
		int min = root.val;
		int max = root.val;
		ReturnData left = process2(root.left);
		ReturnData right = process2(root.right);
		if (left != null) {
			min = Math.min(left.min, min);
			max = Math.max(left.max, max);
		}
		if (right != null) {
			min = Math.min(right.min, min);
			max = Math.max(right.max, max);
		}
		boolean isBST = true;
		if (left != null && (!left.isBST || left.max >= root.val)) {
			isBST = false;
		}
		if (right != null && (!right.isBST || right.min <= root.val)) {
			isBST = false;
		}
		return new ReturnData(min, max, isBST);
	}

	private static int preValue = Integer.MIN_VALUE;

	public boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		boolean left = isValidBST(root.left);
		if (!left) {
			return false;
		}
		if (root.val < preValue) {
			return false;
		} else {
			preValue = root.val;
		}
		return isValidBST(root.right);
	}

	public ListNode reverseList(ListNode head) {
		ListNode prev = null;
		ListNode cur = head;
		while (cur != null) {
			ListNode next = cur.next;
			cur.next = prev;
			prev = cur;
			cur = next;
		}
		head = prev;
		return head;
	}

	public void reorderList(ListNode head) {
		ListNode pre = new ListNode(0);
		ListNode slow = pre;
		ListNode fast = pre;
		pre.next = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		ListNode half = slow.next;
		slow.next = null;
		ListNode rev_half = reverseList(half);
		ListNode cur = pre.next;
		while (rev_half != null) {
			ListNode temp = cur.next;
			cur.next = rev_half;
			cur = cur.next;
			rev_half = rev_half.next;
			cur.next = temp;
			cur = cur.next;
		}
	}

	class Node {
		public int val;
		public Node next;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, Node _next) {
			val = _val;
			next = _next;
		}
	}

	public Node insert(Node head, int insertVal) {
		if (head == null) {
			Node node = new Node(insertVal);
			node.next = node;
			return node;
		}

		Node max = head, min = head;
		Node p = head.next;
		while (p != head) {
			if (p.val > max.val) {
				max = p;
			}
			if (p.val < min.val) {
				min = p;
			}
			p = p.next;
		}
		if (max.val == min.val) {
			head.next = new Node(insertVal, head.next);
		} else if (insertVal >= max.val || insertVal <= min.val) {
			while (max.next.val == max.val) {
				max = max.next;
			}
			max.next = new Node(insertVal, max.next);
		} else {
			while (min.next.val < insertVal) {
				min = min.next;
			}
			min.next = new Node(insertVal, min.next);
		}
		return head;
	}

	public String originalDigits(String s) {
		HashMap<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			map.put(ch, map.getOrDefault(ch, 0) + 1);
		}
		int[] cnt = new int[10];
		cnt[0] = map.getOrDefault('z', 0);
		cnt[2] = map.getOrDefault('w', 0);
		cnt[4] = map.getOrDefault('u', 0);
		cnt[6] = map.getOrDefault('x', 0);
		cnt[8] = map.getOrDefault('g', 0);

		cnt[3] = map.getOrDefault('h', 0) - cnt[8];
		cnt[5] = map.getOrDefault('f', 0) - cnt[4];
		cnt[7] = map.getOrDefault('s', 0) - cnt[6];

		cnt[1] = map.getOrDefault('o', 0) - cnt[0] - cnt[2] - cnt[4];
		cnt[9] = map.getOrDefault('i', 0) - cnt[5] - cnt[6] - cnt[8];

		StringBuilder ans = new StringBuilder();

		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < cnt[i]; j++) {
				ans.append(i);
			}
		}
		return ans.toString();

	}

	public int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		} else {
			int left = maxDepth(root.left);
			int right = maxDepth(root.right);
			return Math.max(left, right) + 1;
		}
	}

	public boolean isValid(String s) {
		int length = s.length();
		if (length % 2 > 0) {
			return false;
		}
		Map<Character, Character> map = new HashMap<>();

		map.put(')', '(');
		map.put(']', '[');
		map.put('}', '{');
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < length; i++) {
			char ch = s.charAt(i);
			if (map.containsKey(ch)) {
				if (stack.isEmpty() || !stack.peek().equals(map.get(ch))) {
					return false;
				}
				stack.pop();
			} else {
				stack.push(ch);
			}
		}
		return stack.isEmpty();
	}

	public TreeNode sortedArrayToBST(int[] nums) {
		return helper(nums, 0, nums.length - 1);
	}

	public TreeNode helper(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}

		// 总是选择中间位置左边的数字作为根节点
		int mid = left + (right - left) / 2;

		TreeNode root = new TreeNode(nums[mid]);
		root.left = helper(nums, left, mid - 1);
		root.right = helper(nums, mid + 1, right);
		return root;
	}

	public TreeNode searchBST(TreeNode root, int val) {
		if (root == null) {
			return null;
		}
		if (root.val == val) {
			return root;
		} else if (root.val < val) {
			return searchBST(root.right, val);
		} else {
			return searchBST(root.left, val);
		}
	}

	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		for (String c : tokens) {
			switch (c) {
				case "+":
				case "-":
				case "*":
				case "/":
					int num2 = stack.pop();
					int num1 = stack.pop();
					stack.push(calc(num1, num2, c));
					break;
				default:
					stack.push(Integer.parseInt(c));
			}
		}
		return stack.pop();
	}

	private int calc(int a, int b, String op) {
		switch (op) {
			case "+":
				return a + b;
			case "-":
				return a - b;
			case "*":
				return a * b;
			default:
				return a / b;
		}
	}

	public int[] asteroidCollision(int[] asteroids) {
		int i = 0;
		// 设置一个辅助栈
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		while (i < asteroids.length) {
			// 如果当前栈为空，或者当前 i 指向的元素大于0，则直接进栈。
			if (stack.isEmpty() || asteroids[i] > 0) {
				stack.push(asteroids[i]);
				// 如果栈不为空，且当前元素小于0, 分几种情况。
			} else {
				// 1. 如果栈顶元素 < 0 , 则直接将当前元素入栈，同时 i 指向下一个元素
				if (stack.peek() < 0) {
					stack.push(asteroids[i]);
				} else {
					// 如果栈顶元素 > 0 , 则先将栈顶元素弹出
					Integer pop = stack.pop();
					// 如果弹出的栈顶元素比当前元素的绝对值小，则弹出的这个行星爆炸，当前元素（行星）不动
					if (pop < Math.abs(asteroids[i])) {
						continue;
						// 如果弹出的栈顶元素比当前元素的绝对值大，则当前行星（元素）爆炸，将弹出的元素压入栈，i 指向下一个元素
					} else if (pop > Math.abs(asteroids[i])) {
						stack.push(pop);
					}
					// 如果弹出的栈顶元素和当前元素的绝对值相等，则两个行星都爆炸，i 指向下一个元素
				}
			}
			i++;
		}

		// 将栈复制到数组中
		int[] ans = new int[stack.size()];
		for (int j = ans.length - 1; j >= 0; j--) {
			ans[j] = stack.pop();
		}
		return ans;
	}


	public static class Info {
		public int maxSumDistance;

		public Info(int maxSumDistance) {
			this.maxSumDistance = maxSumDistance;
		}
	}

	public int maxPathSum(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return root.val;
		} else {
			return process3(root).maxSumDistance;
		}
	}

	public Info process3(TreeNode root) {
		if (root == null) {
			return new Info(0);
		}
		Info left = root.left != null ? process3(root.left) : new Info(0);
		Info right = root.right != null ? process3(root.right) : new Info(0);

		int maxSumDistance = root.val + left.maxSumDistance + right.maxSumDistance;
		int result = Math.max(maxSumDistance, Math.max(left.maxSumDistance, right.maxSumDistance));
		return new Info(result);
	}

	public int sumNumbers(TreeNode root) {
		return dfs(root, 0);
	}

	private int dfs(TreeNode root, int preValue) {
		if (root == null) {
			return 0;
		}
		int sum = root.val + preValue * 10;
		if (root.left == null && root.right == null) {
			return sum;
		} else {
			return dfs(root.left, sum) + dfs(root.right, sum);
		}
	}

	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				if (i == size - 1) {
					result.add(node.val);
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return result;
	}

	public List<Integer> largestValues(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		List<Integer> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		queue.add(root);
		while (!queue.isEmpty()) {
			int max = Integer.MIN_VALUE;
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				max = Math.max(max, size);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			result.add(max);
		}
		return result;
	}

	public int singleNumber(int[] nums) {
		int single = 0;
		for (int num : nums) {
			single ^= num;
		}
		return single;
	}

	public boolean wordBreak(String s, List<String> wordDict) {

		Set<String> wordDictSet = new HashSet(wordDict);
		boolean[] dp = new boolean[s.length() + 1];
		dp[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			for (int j = 0; j < i; j++) {
				if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}

	public TreeNode pruneTree(TreeNode root) {
		if (root == null) {
			return root;
		}
		root.left = pruneTree(root.left);
		root.right = pruneTree(root.right);
		if (root.val == 0 && root.left == null && root.right == null) {
			root = null;
		}
		return root;
	}

	public int maxPower(String s) {
		int ans = 1;
		int cnt = 1;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == s.charAt(i + 1)) {
				++cnt;
				ans = Math.max(ans, cnt);
			} else {
				cnt = 1;
			}
		}
		return ans;
	}

	private TreeNode restNode;

	public TreeNode increasingBST(TreeNode root) {
		TreeNode dummyNode = new TreeNode(-1);
		restNode = dummyNode;
		inorder(root);
		return dummyNode.right;
	}

	private void inorder(TreeNode root) {
		if (root == null) {
			return;
		}
		inorder(root.left);
		restNode.right = root;
		root.left = null;
		restNode = root;
		inorder(root.right);
	}

	private int result = Integer.MIN_VALUE;

	public int maxPathSum2(TreeNode root) {
		if (root == null) {
			return 0;
		}
		process4(root);
		return result;
	}

	private int process4(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = Math.max(0, process4(root.left));
		int right = Math.max(0, process4(root.right));
		result = Math.max(result, left + right + root.val);
		return root.val + Math.max(left, right);
	}

	public boolean canPermutePalindrome(String s) {
		Map<Character, Integer> map = new HashMap<>();

		char[] charArray = s.toCharArray();
		for (char c : charArray) {
			map.put(c, map.getOrDefault(c, 0) + 1);
		}
		int odd = 0;
		for (Integer value : map.values()) {
			if (value % 2 == 1) {
				if (++odd > 1) {
					return false;
				}
			}
		}
		return true;
	}

	public int pathSum(TreeNode root, int targetSum) {
		if (root == null) {
			return 0;
		}

		int ret = rootSum(root, targetSum);
		ret += pathSum(root.left, targetSum);
		ret += pathSum(root.right, targetSum);
		return ret;
	}

	public int rootSum(TreeNode root, int targetSum) {
		int ret = 0;

		if (root == null) {
			return 0;
		}
		int val = root.val;
		if (val == targetSum) {
			ret++;
		}

		ret += rootSum(root.left, targetSum - val);
		ret += rootSum(root.right, targetSum - val);
		return ret;
	}

	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null & root.right == null) {
			return sum == root.val;
		}
		return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
	}

	public void rotate(int[][] matrix) {
		int tR = 0;
		int tC = 0;
		int dR = matrix.length - 1;
		int dC = matrix[0].length - 1;
		while (tR < dR) {
			rotateEdge(matrix, tR++, tC++, dR--, dC--);
		}
		printMatrix(matrix);
	}

	private void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
		int times = dC - tC;
		int tmp = 0;
		for (int i = 0; i < times; i++) {
			tmp = matrix[tR][tC + i];
			matrix[tR][tC + i] = matrix[dR - i][tC];
			matrix[dR - i][tC] = matrix[dR][dC - i];
			matrix[dR][dC - i] = matrix[tR + i][dC];
			matrix[tR + i][dC] = tmp;
		}
	}


	public void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}


	public void rotate2(int[][] matrix) {
		int n = matrix.length;
		for (int i = 0; i < n / 2; ++i) {
			for (int j = 0; j < (n + 1) / 2; ++j) {
				int temp = matrix[i][j];
				matrix[i][j] = matrix[n - j - 1][i];
				matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
				matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
				matrix[j][n - i - 1] = temp;
			}
		}
	}

	public int largestSumAfterKNegations(int[] nums, int k) {
		Map<Integer, Integer> freq = new HashMap<>();
		for (int num : nums) {
			freq.put(num, freq.getOrDefault(num, 0) + 1);
		}
		int ans = Arrays.stream(nums).sum();
		for (int i = -100; i < 0; ++i) {
			if (freq.containsKey(i)) {
				int ops = Math.min(k, freq.get(i));
				ans += (-i) * ops * 2;
				freq.put(i, freq.get(i) - ops);
				freq.put(-i, freq.getOrDefault(-i, 0) + ops);
				k -= ops;
				if (k == 0) {
					break;
				}
			}
		}
		if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
			for (int i = 1; i <= 100; ++i) {
				if (freq.containsKey(i)) {
					ans -= i * 2;
					break;
				}
			}
		}
		return ans;
	}

	public void deleteNode(ListNode node) {
		node.val = node.next.val;
		node.next = node.next.next;
	}

	public int[] topKFrequent(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int num : nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
		PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[2]);

		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			int num = entry.getKey();
			int count = entry.getValue();
			if (queue.size() == k) {
				if (queue.peek()[1] < count) {
					queue.poll();
					queue.offer(new int[]{num, count});
				}
			} else {
				queue.offer(new int[]{num, count});
			}
		}
		int[] result = new int[k];
		for (int i = 0; i < k; i++) {
			result[i] = queue.poll()[0];
		}
		return result;
	}

	public String truncateSentence(String s, int k) {
		String[] strings = s.split(" ");
		String result = "";
		for (int i = 0; i < k; i++) {
			if (i == k - 1) {
				result += strings[i];
				break;
			}
			result = result + strings[i] + " ";
		}
		return result;
	}

	class Trie {
		private Trie[] children;
		private boolean isEnd;

		public Trie() {
			children = new Trie[26];
			isEnd = false;
		}

		public void insert(String word) {
			Trie node = this;
			for (int i = 0; i < word.length(); i++) {
				char ch = word.charAt(i);
				int index = ch - 'a';
				if (node.children[index] == null) {
					node.children[index] = new Trie();
				}
				node = node.children[index];
			}
			node.isEnd = true;
		}

		public boolean search(String word) {
			Trie node = searchPrefix(word);
			return node != null && node.isEnd;
		}

		public boolean startsWith(String prefix) {
			return searchPrefix(prefix) != null;
		}

		private Trie searchPrefix(String prefix) {
			Trie node = this;
			for (int i = 0; i < prefix.length(); i++) {
				char ch = prefix.charAt(i);
				int index = ch - 'a';
				if (node.children[index] == null) {
					return null;
				}
				node = node.children[index];
			}
			return node;
		}
	}

	public int longestValidParentheses(String s) {
		int maxans = 0;
		int[] dp = new int[s.length()];
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) == ')') {
				if (s.charAt(i - 1) == '(') {
					dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
				} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
					dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
				}
				maxans = Math.max(maxans, dp[i]);
			}
		}
		return maxans;
	}

	public String shortestCompletingWord(String licensePlate, String[] words) {
		int[] cnt = new int[26];
		for (int i = 0; i < licensePlate.length(); ++i) {
			char ch = licensePlate.charAt(i);
			if (Character.isLetter(ch)) {
				++cnt[Character.toLowerCase(ch) - 'a'];
			}
		}

		int idx = -1;
		for (int i = 0; i < words.length; ++i) {
			int[] c = new int[26];
			for (int j = 0; j < words[i].length(); ++j) {
				char ch = words[i].charAt(j);
				++c[ch - 'a'];
			}
			boolean ok = true;
			for (int j = 0; j < 26; ++j) {
				if (c[j] < cnt[j]) {
					ok = false;
					break;
				}
			}
			if (ok && (idx < 0 || words[i].length() < words[idx].length())) {
				idx = i;
			}
		}
		return words[idx];
	}

	public ListNode mergeKLists(ListNode[] lists) {
		ListNode x = null;
		for (ListNode listnode : lists) {
			x = merge(x, listnode);
		}
		return x;
	}

	private ListNode merge(ListNode a, ListNode b) {
		ListNode dummy = new ListNode(-1);
		ListNode x = dummy;
		while (a != null && b != null) {
			if (a.val < b.val) {
				x.next = a;
				a = a.next;
			} else {
				x.next = b;
				b = b.next;
			}
			x = x.next;
		}
		if (a != null) {
			x.next = a;
		}
		if (b != null) {
			x.next = b;
		}
		return dummy.next;
	}

	public ListNode sortList(ListNode head) {
		PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
		while (head != null) {
			heap.offer(head);
			head = head.next;
		}
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		while (!heap.isEmpty()) {
			cur.next = heap.poll();
			cur = cur.next;
		}
		cur.next = null;
		return dummy.next;
	}

	public int findKthLargest(int[] nums, int k) {
		int n = nums.length;
		int l = 0;
		int r = n - 1;
		while (true) {
			int idx = partition(nums, l, r);
			//noinspection ControlFlowStatementWithoutBraces
			if (idx == k - 1) {
				return nums[idx];
			} else if (idx < k - 1) {
				l = idx + 1;
			} else {
				r = idx - 1;
			}
		}

	}

	//----左右交换
	public int partition(int[] nums, int l, int r) {
		int pivot = nums[l];
		int begin = l;
		while (l < r) {
			while (l < r && nums[r] <= pivot) {
				r--;
			}
			while (l < r && nums[l] >= pivot) {
				l++;
			}
			if (l < r) {
				int tmp = nums[l];
				nums[l] = nums[r];
				nums[r] = tmp;
			}
		}

		int tmp = nums[begin];
		nums[begin] = nums[l];
		nums[l] = tmp;
		return l;
	}

	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		TreeNode left = invertTree(root.left);
		TreeNode right = invertTree(root.right);
		root.left = right;
		root.right = left;
		return root;
	}

	public void rotate(int[] nums, int k) {
		k %= nums.length;
		reverse(nums, 0, nums.length - 1);
		reverse(nums, 0, k - 1);
		reverse(nums, k, nums.length - 1);
	}

	public void reverse(int[] nums, int start, int end) {
		while (start < end) {
			int temp = nums[start];
			nums[start] = nums[end];
			nums[end] = temp;
			start += 1;
			end -= 1;
		}
	}

	public int[] productExceptSelf(int[] nums) {
		int length = nums.length;
		int[] answer = new int[length];

		// answer[i] 表示索引 i 左侧所有元素的乘积
		// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
		answer[0] = 1;
		for (int i = 1; i < length; i++) {
			answer[i] = nums[i - 1] * answer[i - 1];
		}

		// R 为右侧所有元素的乘积
		// 刚开始右边没有元素，所以 R = 1
		int R = 1;
		for (int i = length - 1; i >= 0; i--) {
			// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
			answer[i] = answer[i] * R;
			// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
			R *= nums[i];
		}
		return answer;
	}

	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		helpers(res, nums, new ArrayList<Integer>(), 0);
		return res;
	}

	private void helpers(List<List<Integer>> res, int[] nums, ArrayList<Integer> list, int index) {
		if (index == nums.length) {
			res.add(new ArrayList<>(list));
			return;
		}
		helpers(res, nums, list, index + 1);
		list.add(nums[index]);
		helpers(res, nums, list, index + 1);
		list.remove(list.size() - 1);
	}

	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		int length = candidates.length;
		List<List<Integer>> res = new ArrayList<>();
		Arrays.sort(candidates);
		dfs1(candidates, length, 0, target, new ArrayList<Integer>(), res);
		return res;
	}

	private void dfs1(int[] candidates, int n, int index, int target, ArrayList<Integer> list, List<List<Integer>> res) {
		if (target == 0) {
			res.add(new ArrayList<>(list));
			return;
		}
		for (int i = index; i < n; i++) {
			if (candidates[i] > target) {
				break;
			}
			if (i > index && candidates[i] == candidates[i - 1]) {
				continue;
			}
			list.add(candidates[i]);
			dfs1(candidates, n, index + 1, target - candidates[i], list, res);
			list.remove(list.size() - 1);
		}
	}


	String s;
	int n;
	List<String> res = new ArrayList<>();
	List<String> path = new ArrayList<>();

	public List<String> restoreIpAddresses(String s) {
		this.s = s;
		this.n = s.length();
		if (n < 4 || n > 12) {
			return res;
		}
		backtrace(0);
		return res;
	}

	public void backtrace(int idx) {
		if (path.size() == 4) {
			if (idx == n) {
				String cur = String.join(".", path);
				res.add(cur);
			}
			return;
		}
		if (idx == n) {
			return;
		}

		if (s.charAt(idx) == '0') {
			path.add("0");
			backtrace(idx + 1);
			path.remove(path.size() - 1);
		} else {
			for (int i = idx; i < n; i++) {
				int cur_num = Integer.parseInt(s.substring(idx, i + 1));
				if (0 <= cur_num && cur_num <= 255) {
					path.add(s.substring(idx, i + 1));
					backtrace(i + 1);
					path.remove(path.size() - 1);
				} else {
					break;
				}
			}
		}
	}

	public String[][] partition(String s) {
		int n = s.length();
		char[] arr = s.toCharArray();
		// 预处理
		boolean[][] dp = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = true;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				dp[i][j] = (arr[i] == arr[j] && dp[i + 1][j - 1]);
			}
		}
		List<List<String>> res = new ArrayList<>();
		List<String> path = new ArrayList<>();
		dfs(res, path, s, n, dp, 0);
		// List<List<String>> 转 String[][]，这里不重要
		String[][] ans = new String[res.size()][];
		for (int i = 0; i < res.size(); i++) {
			ans[i] = new String[res.get(i).size()];
			for (int j = 0; j < ans[i].length; j++) {
				ans[i][j] = res.get(i).get(j);
			}
		}
		return ans;
	}

	public void dfs(List<List<String>> res, List<String> path, String s, int n, boolean[][] dp, int pos) {
		if (pos == n) {
			res.add(new ArrayList<>(path));
			return;
		}
		for (int i = pos; i < n; i++) {
			// s[pos:i] （闭区间）是一个回文，所以递归搜索s[i+1, s.length()-1]
			if (dp[pos][i]) {
				path.add(s.substring(pos, i + 1));
				dfs(res, path, s, n, dp, i + 1);
				path.remove(path.size() - 1);
			}
		}
	}

	public boolean checkSubTree(TreeNode t1, TreeNode t2) {
		if (t1 == null) {
			return t2 == null;
		}
		return isSame(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
	}

	private boolean isSame(TreeNode t1, TreeNode t2) {
		if (t1 == null && t2 == null) {
			return true;
		}
		if (t1 == null || t2 == null) {
			return false;
		}
		return t1.val == t2.val && isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
	}


	Map<TreeNode, Integer> dp = new HashMap<>();

	public int rob(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (dp.containsKey(root)) {
			return dp.get(root);
		}
		/**
		 * 选择打劫这个房子
		 */
		int ans = root.val;
		if (null != root.left) {
			ans += rob(root.left.left) + rob(root.left.right);
		}
		if (null != root.right) {
			ans += rob(root.right.left) + rob(root.right.right);
		}
		/**
		 * 不抢劫这个房子
		 */
		ans = Math.max(ans, rob(root.left) + rob(root.right));
		dp.put(root, ans);
		return ans;
	}

	public int rob2(TreeNode root) {
		if (root == null) {
			return 0;
		}

		int money = root.val;
		if (root.left != null) {
			money += (rob(root.left.left) + rob(root.left.right));
		}

		if (root.right != null) {
			money += (rob(root.right.left) + rob(root.right.right));
		}

		return Math.max(money, rob(root.left) + rob(root.right));
	}

	public boolean isCompleteTree(TreeNode root) {
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		boolean reachNull = false;
		q.add(root);
		while (!q.isEmpty()) {
			TreeNode node = q.poll();
			if (node == null) {
				reachNull = true;
			}
			if (node != null) {
				if (reachNull) {
					return false;
				}
				q.add(node.left);
				q.add(node.right);
			}
		}
		return true;
	}

	public void wiggleSort(int[] nums) {
		int[] bucket = new int[5001];
		for (int num : nums) {
			bucket[num]++;
		}
		int len = nums.length;
		int small, big;
		//穿插数字时的上界
		//总长度为奇数时，“小 大 小 大 小”边界左右都为较小的数；
		//总长度为偶数时，“小 大 小 大”边界左为较小的数，边界右为较大的数
		if ((len & 1) == 1) {
			small = len - 1;
			big = len - 2;
		} else {
			small = len - 2;
			big = len - 1;
		}
		int j = 5000; //从后往前，将桶中数字穿插到数组中，后界为j
		//桶中大的数字在后面，小的数字在前面，所以先取出较大的数字，再取出较小的数字
		//先将桶中的较大的数字穿插放在nums中
		for (int i = 1; i <= big; i += 2) {
			while (bucket[j] == 0) {
				j--;//找到不为0的桶
			}
			nums[i] = j;
			bucket[j]--;
		}
		//再将桶中的较小的数字穿插放在nums中
		for (int i = 0; i <= small; i += 2) {
			while (bucket[j] == 0) {
				j--;//找到不为0的桶
			}
			nums[i] = j;
			bucket[j]--;
		}
	}

	public ListNode oddEvenList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode evenHead = head.next;
		ListNode odd = head, even = evenHead;
		while (even != null && even.next != null) {
			odd.next = even.next;
			odd = odd.next;
			even.next = odd.next;
			even = even.next;
		}
		odd.next = evenHead;
		return head;
	}

	public int minSubArrayLen(int target, int[] nums) {
		int length = nums.length;
		if (length == 0) {
			return 0;
		}
		int ans = Integer.MAX_VALUE;
		int start = 0;
		int end = 0;
		int sum = 0;
		while (end < n) {
			sum += nums[end];
			while (sum >= target) {
				ans = Math.min(ans, end - start + 1);
				sum -= nums[start];
				start++;
			}
			end++;
		}
		return ans == Integer.MAX_VALUE ? 0 : ans;
	}

	public int findMagicIndex(int[] nums) {
		for (int i = 0; i < nums.length; i++) {
			if (i == nums[i]) {
				return i;
			}
		}
		return -1;
	}

	public boolean isEvenOddTree(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		int level = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			int preValue = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				int curValue = node.val;
				if (level % 2 == curValue % 2) {
					return false;
				}
				if ((level % 2 == 0 && curValue < preValue) || (level % 2 == 1 && curValue >= preValue)) {
					return false;
				}
				preValue = curValue;
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			level++;
		}
		return true;
	}

	private int N;

	public boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if ((sum & 1) == 1) {
			return false;
		}
		N = nums.length;
		sum >>= 1;
		Boolean[][] dp = new Boolean[n + 1][sum + 1];
		return dfsCanPartition(nums, dp, 0, sum);
	}

	private boolean dfsCanPartition(int[] nums, Boolean[][] dp, int index, int left) {
		if (index == N) {
			dp[index][left] = left == 0;
			return dp[index][left];
		}
		if (dp[index][left] != null) {
			return dp[index][left];
		}
		int sub = left = nums[index];
		if (sub == 0) {
			return true;
		}
		if (sub > 0) {
			if (dfsCanPartition(nums, dp, index + 1, sub)) {
				return true;
			}
		}
		if (dfsCanPartition(nums, dp, index + 1, left)) {
			return true;
		}
		dp[index][left] = false;
		return false;
	}

	public String[] findOcurrences(String text, String first, String second) {
		String[] textWords = text.split(" ");
		List<String> list = new ArrayList<>();
		for (int i = 2; i < textWords.length; i++) {
			if (textWords[i - 2].equals(first) && textWords[i - 1].equals(second)) {
				list.add(textWords[i]);
			}
		}
		String[] ans = new String[list.size()];
		for (int i = 0; i < list.size(); i++) {
			ans[i] = list.get(i);
		}
		return ans;
	}

	public int findString(String[] words, String s) {
		int left = 0;
		int right = words.length - 1;
		int mid = left + (right - left) >> 1;
		if ("".equals(words[mid])) {
			if (words[right].equals(s)) {
				return right;
			}
			right--;
		} else if (words[mid].equals(s)) {
			return mid;
		} else if (words[mid].compareTo(s) < 0) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
		return -1;
	}

	public List<Integer> findDisappearedNumbers(int[] nums) {
		int length = nums.length;
		for (int num : nums) {
			int x = (num - 1) % length;
			nums[x] += length;
		}
		List<Integer> ans = new ArrayList<>();
		for (int i = 0; i < length; i++) {
			if (nums[i] <= length) {
				ans.add(i + 1);
			}
		}
		return ans;
	}

	public boolean isPalindrome(int x) {
		if (x < 0 || (x % 10 == 0 && x != 0)) {
			return false;
		}
		int revNumber = 0;
		while (x > revNumber) {
			revNumber = revNumber * 10 + x % 10;
			x /= 10;
		}
		return x == revNumber || x == revNumber / 10;
	}

}
